//
// Created by liushuai on 2021/2/2.
//

<<<<<<< HEAD:cxx/algorithm/src/search.cc
#include "search.h"

int findMinIndex(int* num,int n) {
    if (n<=0)
=======
#include "common.h"
namespace common {

int findMinIndex(int *num, int n) {
    if (n <= 0)
>>>>>>> dev:cxx/algorithm/common/src/search.cc
        return -1;
    int start = 0;
    int end = n - 1;
    while (start < end) {
        int mid = (end - start) / 2 + start;
        if (num[mid] < num[end])
            end = mid;
        else
            start = mid + 1;
    }
    return start;
}
<<<<<<< HEAD:cxx/algorithm/src/search.cc
int binarySearch(int* num,int start,int end,int target){
    while(start<end){
        int mid = (end-start)/2+start;
        if(num[mid] > target)
            end = mid-1;
        else
            start = mid+1;
=======
int binarySearch(int *num, int start, int end, int target) {
    while (start < end) {
        int mid = (end - start) / 2 + start;
        if (num[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
>>>>>>> dev:cxx/algorithm/common/src/search.cc
    }
    return start;
}

<<<<<<< HEAD:cxx/algorithm/src/search.cc
int search(int* num, int n, int target) {
    if(n<=0)
        return -1;
    else{
        int rotate = findMinIndex(num,n);
        int start = 0;
        int end = n-1;

        if (num[end] >= num[rotate]) {
            return binarySearch(num,rotate,end,target);
        } else
            return binarySearch(num,start,rotate-1,target);
    }
}
=======
int search(int *num, int n, int target) {
    if (n <= 0)
        return -1;
    else {
        int rotate = findMinIndex(num, n);
        int start = 0;
        int end = n - 1;

        if (num[end] >= num[rotate]) {
            return binarySearch(num, rotate, end, target);
        } else
            return binarySearch(num, start, rotate - 1, target);
    }
}

int findMinIndex(std::vector<int> &nums) {
    int n = nums.size();
    int left = 0;
    int right = n - 1;
    int mid = 0;
    while (left < right) {
        mid = left + ((right - left) >> 1);
        if (nums[mid] >= nums[right])
            left = mid + 1;
        else {
            right = mid;
        }
    }
    return left;
}

int binarySearch(std::vector<int> &num, int start, int end, int target) {
    int result = -1;
    if (start == end) {
        if (num[start] == target)
            result = start;
        return result;
    }
    while (start <= end) {
        int mid = start + ((end - start) >> 1);
        if (num[mid] == target) {
            result = mid;
            break;
        } else if (num[mid] < target)
            start = mid + 1;
        else {
            end = mid - 1;
        }
    }
    return result;
}
int search(std::vector<int> &nums, int target) {
    if (nums.empty())
        return -1;
    int left = findMinIndex(nums);
    int right = nums.size() - 1;
    if (left == 0)
        return binarySearch(nums, left, right, target);
    else {

        if (nums[0] > target)
            return binarySearch(nums, left, right, target);
        else {
            return binarySearch(nums, 0, left - 1, target);
        }
    }
}
} // namespace common
>>>>>>> dev:cxx/algorithm/common/src/search.cc
